/**
 * @author: Colmenares Carlos (carlos.a.colmenares.r@gmail.com)
 *
 * Solver for the n-queens problem
 */
#include "n_queens_solver.h"

int main(int argc, char *argv[]) {

    //Parse the arguments
    if( argc < 2 ) {
        print_usage();
        exit(1);
    }
    N = atoi(argv[1]);
    if( N < 4 ) {
        printf("There is no solution for a board of size %d, please\n",N);
        printf("select an integer greater than 3 ");
        exit(1);
    }

    {
        int i = 2;
        while(i<argc){

            if(strcmp(argv[i],"-b")==0) {
                print_board = TRUE;
            }
            else if(strcmp(argv[i],"-s")==0) {
                print_solution = TRUE;
            }
            else if(strcmp(argv[i],"-i")==0) {
                print_info = TRUE;
            }
            else {
                print_usage();
                exit(1);
            }
            i++;
        }
    }

    //Initialize arrays
    queens = (int*)malloc( N * sizeof(int) );
    pos_diag = (int*)malloc( (2*N-1) * sizeof(int) );
    neg_diag = (int*)malloc( (2*N-1) * sizeof(int) );
    attacked = (int*)malloc( N * sizeof(int) );

    //Generate an initial board 
    gen_init_board();

    //Initialize statistic variables
    //The initial number of conflicts
    int init_conflicts = tot_conflicts;
    //The global number of effective swaps made
    int tot_swaps = 0;
    //The total number of iterations made
    int tot_iterations = 0;

    //The number of current conflicted queens
    int conflicted = compute_attacks();
    //The limit for recalculating the attacked queens
    int limit = (int)(ceil(tot_conflicts * C1));
    //Number of loops made
    int num_loops = 0;

    srand( (unsigned int)time(NULL) );

    while( tot_conflicts != 0 ) {
        //Take a conflicted queen
        for(int k=0; k<conflicted ; k++) {

            num_loops++;
            if(num_loops%C5==0)
                srand((unsigned int)time(NULL));

            int i = attacked[k];

            //Choose a random queen
            int j;
            j = rand()%N;

            int ci = num_conflicts(i);

            int cj = num_conflicts(j);

            //Test if swapping reduces conflicts
            
            swap_queens(i,j);
            //New conflicts
            int n_ci = num_conflicts(i);
            int n_cj = num_conflicts(j);

            //Check if it is better
            int delta = ci + cj - (n_ci + n_cj);  

            if( delta > 0 ){ //Good swap
                tot_swaps++;
                tot_conflicts -= 2*delta;

                if(tot_conflicts == 0)
                    break;
                
                if( k>C3 && tot_conflicts < limit ) { 
                    limit = (int)(ceil(tot_conflicts * C1));
                    conflicted = compute_attacks();
                    break;
                }
            } else { //Bad swap
                //Take them back to place
                swap_queens(i,j);
            }

        }
        //Recalculate if necessary
        if( tot_conflicts < limit ) { 
            limit = (int)(ceil(tot_conflicts * C1));
            conflicted = compute_attacks();
        }

        //If there has been too many swaps and the board hasn't
        //been solved, we're trapped in a local minimum and it's
        //better to randomize the board and start again
        if( num_loops > C2*N ) {
            //printf("Trapped!!!! Randomizing\n");
            randomize_board();
            conflicted = compute_attacks();
            limit = (int)(ceil(tot_conflicts * C1));
            tot_iterations += num_loops;
            num_loops = 0;
        }
    }
    tot_iterations += num_loops;

    printf("Solution found!\n");

    //Now print output information, if necessary

    //Print the resulting board
    if(print_board){
        printf("\nSolution board:\n");
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++)
                printf("%c ",j==queens[i]?'x':'.');
            printf("   ( %d, %d )\n",i,queens[i]);
        }
    }

    //Print the solution
    if(print_solution){
        printf("\nFinal solution:\nRow Column\n");
        for(int i=0;i<N;i++){
            printf("%d %d\n",i,queens[i]);
        }
    }

    //Print algorithm's throughput
    if(print_info){
        printf("\nFinal statistics:\n");
        printf("Initial number of conflicts: %d\n",init_conflicts);
        printf("Number of iterations made: %d\n",tot_iterations);
        printf("Number of queen-swaps made: %d\n",tot_swaps);
    }
    return 0;
}

inline void print_usage(){
    printf("Usage: ./n_queens_solver board_size [OPTIONS]\n");
    printf("      Options:\n");
    printf("         -i      Print additional information about the algorithm\n");
    printf("         -b      Print final board\n");
    printf("         -s      Print final solution: List of (row,column) tuples\n");
}

inline void gen_init_board(){
    //Clear the arrays
    memset( pos_diag, 0, sizeof(int)*(2*N-1));
    memset( neg_diag, 0, sizeof(int)*(2*N-1));

    srand((unsigned int)time(NULL));

    //Create a mask to avoid placing queens
    //on the same column
    const int int_bits = sizeof(int)*8;
    int mask_size = (N+int_bits-1)/int_bits;
    int *mask = (int*)malloc( mask_size*sizeof(int) );
    memset( mask, 0, mask_size*sizeof(int) );

    //Place queens with no conflicts until
    //C4 retries are needed
    int i_free;
    for(i_free=0; i_free<N; i_free++){
        int retry = 0;
        while(retry < C4){
            int j = rand()%N;
            int d1 = j/int_bits;
            int d2 = j%int_bits;

            if(
                mask[d1]&(1<<d2) ||
                pos_diag[i_free+j] ||
                neg_diag[i_free-j+N-1]
            ){
                retry++;
                continue;
            }

            mask[d1] |= (1<<d2);
            queens[i_free] = j;
            pos_diag[i_free+j]=1; 
            neg_diag[i_free-j+N-1]=1;

            break;
        }
        if(retry==C4)
            break;
    }
    
    //Place the rest of the queens in a random
    //way
    srand((unsigned int)time(NULL));
    int k1=0, k2=0;
    int rest = N - i_free;

    for(int i=0; i<rest; i++){
        while(mask[k1]&(1<<k2)){
            k2++;
            if(k2==int_bits){
                k1++;
                k2=0;
            }
        }
        int j = k1*int_bits + k2;

        //Fisher–Yates' random permutation algorithm
        int k = rand()%(i+1);
        queens[i_free+i] = queens[i_free+k];
        queens[i_free+k] = j;


        k2++;
        if(k2==int_bits){
            k1++;
            k2=0;
        }
    }

    //Place diagonals and count conflicts
    tot_conflicts = 0;
    for(int i=i_free; i<N ; i++){
        tot_conflicts += (pos_diag[ i+queens[i] ]++)*2;
        tot_conflicts += (neg_diag[ i-queens[i]+N-1 ]++)*2;
    }
}

inline int num_conflicts(int y){
    //column of the queen
    int x = queens[y];

    //The number of conflicts that generates
    //the queens
    int conf = 0;

    //Check the number of other queens in your diagonals
    conf += pos_diag[ y+x ] - 1;
    conf += neg_diag[ y-x + N-1 ] - 1;

    return conf;
}

inline void swap_queens(int a1, int a2){
    //Take out from diagonals
    int col_a1 = queens[a1];
    int col_a2 = queens[a2];

    pos_diag[ a1 + col_a1 ]--;
    neg_diag[ a1 - col_a1 + N-1 ]--;
    
    pos_diag[ a2 + col_a2 ]--;
    neg_diag[ a2 - col_a2 + N-1 ]--;

    //Swap...
    queens[a1] = col_a2;
    queens[a2] = col_a1;
    
    //Put in diagonals
    pos_diag[ a1 + col_a2 ]++;
    neg_diag[ a1 - col_a2 + N-1 ]++;
    
    pos_diag[ a2 + col_a1 ]++;
    neg_diag[ a2 - col_a1 + N-1 ]++;
}

inline int randomize_board(){
    //TODO check the MAXRAND number!
    srand((unsigned int)time(NULL));

    //Fisher–Yates' shuffle algorithm
    for(int i=N-1;i>0;i--){
        int j = rand()%(i+1);
        swap_queens(i,j);
    }

    //Count conflicts
    tot_conflicts = 0;
    for(int i=0; i<N ; i++)
        tot_conflicts += num_conflicts(i);

}


inline int compute_attacks(){
    int k = 0;
    for(int i=0;i<N;i++)
        if(num_conflicts(i) > 0)
            attacked[k++] = i;

    return k;
}
